#! /usr/bin/python

import math
import time
import random
tt = time.time()

_mrpt_num_trials = 5

def tryComposite(a, s, d, n):
    x = pow(a, d, n)
    if x == 1: return False
    for i in range(s):
	x = pow(a, 2**i * d, n)
	if x == n - 1: return False
    return True

def millerRabin(n):
    s = 0
    d = n - 1
    while(d%2 == 0):
         s += 1
	 d /= 2
    k = 0
    for i in range(_mrpt_num_trials):
	a = random.randrange(2, n)
        if tryComposite(a, s, d, n): return False
    return True

def isPrime(n):
    if n ==2 or n==3 or n==5 or n==7: return True
    if n==1 or n%2 == 0 or n%3 == 0: return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n%i == 0 or n%(i+2) == 0: return False
    return True

def sieve(n):
    ll = range(n)
    for i in range(2, int(math.sqrt(n)) + 1):
	for j in range(i**2, n, i):
	    ll[j] = 0
    return [p for p in ll if p != 0]

primes = sieve(100)
setPrimes = set(primes)
table = [0 for i in range(100)]
table[0:10] = [-1, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4]
primes.remove(1)
for p in primes:
    table[p] = p - 1

for i in range(2, 100):
    if table[i] == 0: continue
    for p in primes:
	n = i*p
	if n >= 100: break
	if table[n] != 0: continue	
	if i%p != 0:
	   table[n] = table[i]*(p-1)
	else: table[n] = table[i]*p

#print table

powerof2 = {}

for i in range(26):
    powerof2.setdefault(2**i, []).append(i)

def chainLength(start, table):
    length = 2
    while start != 2:
	start = table[start]
	length += 1
    return length

lenTable = [0 for i in range(4*10**7)]
lenTable[1] = 0
lenTable[2] = 2
for i in range(3, 100, 2):
    lenTable[i] = chainLength(i, table)

print lenTable[0:100]

for i in range(1, 26):
    n = 2**i + 1
    lenTable[n] = i + 2

for j in range(3, 4*10**7, 2):  
    if lenTable[j] > 25: continue  
    for i in range(1, 26):    
	n = 2**i * j + 1
	if n > 4*10**7: break
	if lenTable[n] == 0: lenTable[n] = i + lenTable[j]

print lenTable[0:100]

print lenTable.count(25)
print max(lenTable)
print lenTable[101], lenTable[25], lenTable[9548417]
ss = 0
for i in range(29, len(lenTable), 2):
    if lenTable[i] == 25 and millerRabin(i):
	print i
	ss += i
	break

print ss 
print time.time() - tt
